Removal Game

題目

小明和小花在玩一個遊戲，在桌面上有 $n$ 個數字，從小明開始遊戲。 在每個回合，他們可以挑選這 $n$ 個數字的第一個數字或最後一個數字，並且將它從桌上拿走，這個玩家這時候分數會增加他拿走的數字的量，而對手就不能再繼續拿這個數字了(因為被拿走了)。 如果小明跟小花都用最佳策略去玩這個遊戲，請問小明最多能獲得幾分?

輸入

• 第一行只有一個數字 $n$ ($1 \le n \le 5000$)
• 第二行有 $n$ 個數字 $x_1$, $x_2$,...$x_n$ ($-10^9 \le x_i \le 10^9$)

輸出

輸出小明最多能獲得的分數

範例測資

Input:
4
4 5 1 3

Output:
8

觀察

題目給的 $n$ 個數字排在一起是一個區間。

想法

首先把題目拆成一個個的小題目，也就是說，題目是問區間 $1$ ~ $n$ 時，小明最多能得幾分，你就可以拆成更小的區間時，小名最多能得幾分，然後利用小題目的答案來組出大題目的答案，最後得到區間 $1$ ~ $n$時，小明最多能得多少分。

使用上面的方法，可以用長度 $x-1$ 區間的最佳答案組出 $x$ 區間的最佳答案，但是有一個問題，當長度 $x-1$ 區間的最佳答案和長度 $x$ 區間的最佳答案是針對不一樣的玩家的最佳答案。

假設區間 $x-1$ 是針對玩家 $A$ 的最佳答案，區間 $x$ 是針對玩家 $B$ 的最佳達，你會需要用一個前綴和來快速得到每個區間的總和，然後使用這個總和減掉 $x-1$ 區間的最佳答案來代表 $x-1$ 對於玩家 $B$ 的最佳答案

由於你要遍歷所有區間，所以時間複雜度是 $O(n^2)$。

範例程式碼

C++ 範例

#include <bits/stdc++.h>
using namespace std;
long long int dp[5010][5010];
long long int a[5010];
long long int Pre[5010];
void rec(int l,int r){
    if(l == r){
        dp[l][r] = a[l];
        return;
    }
    if(dp[l + 1][r] == -1e18) rec(l + 1, r);
    dp[l][r] = max(dp[l][r], a[l] + Pre[r] - Pre[l] - dp[l + 1][r]);
    if(dp[l][r - 1] == -1e18) rec(l, r - 1);
    dp[l][r] = max(dp[l][r], a[r] + Pre[r - 1] - Pre[l - 1] - dp[l][r - 1]);
    return;
}
int main() {
    for(int i = 1; i <= 5000; i++) {
        for(int j = 1; j <= 5000; j++) {
            dp[i][j] = -1e18;
        }
    }
    int n;
    cin >> n;
    for(int i = 1; i <=n ; i++) {
        cin >> a[i];
        Pre[i] = a[i] + Pre[i - 1];
    }
    rec(1, n);
    cout << dp[1][n];
    return 0;
}